package tree

// 94、105、106、115，116、450、889

const (
	left byte = iota
	right
)

type Node[R comparable] struct {
	Left, Right *Node[R]
	Value       R
	hash        uint32
}

func (n *Node[R]) getChildren() []*Node[R] {
	children := make([]*Node[R], 2)
	if n.Left != nil {
		children[0] = n.Left
	}
	if n.Right != nil {
		children[1] = n.Right
	}
	return children
}

type BinarySearchTree[R comparable] struct {
	root *Node[R]
}

func (b *BinarySearchTree[R]) Search(val R) *Node[R] {
	hash := Hash(val)
	for node := b.root; node != nil; {
		if hash < node.hash {
			node = node.Left
		} else if hash > node.hash {
			node = node.Right
		} else {
			if node.Value == val {
				return node
			}
			node = node.Right
		}
	}
	return nil
}

func (b *BinarySearchTree[R]) Insert(val R) {
	hash := Hash(val)
	if b.root == nil {
		b.root = &Node[R]{Value: val, hash: hash}
		return
	}

	node := b.root
	for {
		if node.hash <= hash {
			if node.Right == nil {
				node.Right = &Node[R]{Value: val, hash: hash}
				return
			}
			node = node.Right
		} else {
			if node.Left == nil {
				node.Left = &Node[R]{Value: val, hash: hash}
				return
			}
			node = node.Left
		}
	}
}

func (b *BinarySearchTree[R]) remove(parent, node *Node[R], dir byte) {
	var n *Node[R]
	if node.Left != nil && node.Right != nil {
		// 找到该节点右子树的最小节点，然后将次最小节点移动到待删除节点的位置
		min, minParent := b.findMinNode(node)
		if node != minParent {
			minParent.Left = min.Right
			min.Right = node.Right
		}
		min.Left = node.Left
		n = min
	} else if node.Left != nil || node.Right != nil {
		n = node.Left
		if node.Right != nil {
			n = node.Right
		}
	}
	if b.root == node {
		b.root = n
		return
	}

	if dir == left {
		parent.Left = n
	} else {
		parent.Right = n
	}
}

func (b *BinarySearchTree[R]) findMinNode(node *Node[R]) (*Node[R], *Node[R]) {
	parent := node
	n := node.Right
	for {
		if n.Left == nil {
			break
		}
		parent = n
		n = n.Left
	}
	return n, parent
}

func (b *BinarySearchTree[R]) Remove(val R) bool {
	hash := Hash(val)
	var parent *Node[R]
	var dir byte

	for node := b.root; node != nil; {
		if hash < node.hash {
			parent = node
			node = node.Left
			dir = left
		} else if hash > node.hash {
			parent = node
			node = node.Right
			dir = right
		} else {
			if node.Value == val {
				b.remove(parent, node, dir)
				return true
			}
			parent = node
			node = node.Right
			dir = right
		}
	}
	return false
}
